package bin_tree.leetcode;

/**
 * @author yuisama
 * @date 2023/03/24 19:34
 * 判断是否是子树
 **/
public class Num572_IsSubTree {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // base case
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null || subRoot == null) {
            return false;
        }
        // 若当前以root为根的树和以subRoot为根的树是相同的树
        if (isSameTree(root,subRoot)) {
            return true;
        }
        // 要么在左子树中包含或者在右子树中包含即可~
        // 千万注意，左子树和右子树的判断，不是判断相同
        return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 1.base case
        if (p == null && q == null) {
            return true;
        }
        // 一个是空树一个非空
        if (p == null || q == null) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        // 继续判断左子树和右子树是否相同
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}